\documentclass[twoside,a4paper]{ctexart}
\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{booktabs}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage{layout}
\usepackage[ruled,linesnumbered,lined,boxed,commentsnumbered]{algorithm2e}

% some common command
\newcommand{\dif}{\mathrm{d}}
\newcommand{\avg}[1]{\left\langle #1 \right\rangle}
\newcommand{\difFrac}[2]{\frac{\dif #1}{\dif #2}}
\newcommand{\pdfFrac}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\OFL}{\mathrm{OFL}}
\newcommand{\UFL}{\mathrm{UFL}}
\newcommand{\fl}{\mathrm{fl}}
\newcommand{\op}{\odot}
\newcommand{\Eabs}{E_{\mathrm{abs}}}
\newcommand{\Erel}{E_{\mathrm{rel}}}

\begin{document}

\pagestyle{fancy}
\fancyhead{}
\lhead{邵柯欣}
\chead{Numerical Analysis}
\rhead{\today}

\section*{I. Solving Nonlinear Equations}
对于连续函数$f: \mathbb{R} \to \mathbb{R}$,求解根$x_0$.
\subsection{[二分法]\textbf{The bisection method}}
Preconditions: $sgn(f(a)) \ne sgn(f(b))$.

Input: $f:[a,b] \to \mathbb{R}$, $a \in \mathbb{R}$, $b \in \mathbb{R}$, $M \in \mathbb{N}$, $\delta \in \mathbb{R}^+$, $\epsilon \in \mathbb{R}^+$

Output: c, h, k

Postconditions: $|f(c)| < \epsilon$ or $|h| < \delta$ or $k = M$

\IncMargin{1em}
\begin{algorithm}
  \caption{二分法实现算法}\label{algorithm1}
  \KwData{$f:[a,b] \to \mathbb{R}$, $a \in \mathbb{R}$, $b \in \mathbb{R}$, $M \in \mathbb{N}$, $\delta \in \mathbb{R}^+$, $\epsilon \in \mathbb{R}^+$
  }
  \KwResult{c, h, k}
  \BlankLine
  \emph{$u \gets f(a)$}\;
  \emph{$v \gets f(b)$}\;
  \For{$k = 0:M$}{
    \emph{$h \gets b-a$}\;
    \emph{$c \gets a + h/2$}\;
    \lIf{$|h| < \delta$ or $k == M$}{break}
    \emph{$w \gets f(c)$}\;
    \uIf{$|w| < \epsilon$}{break}
    \uElseIf{$sgn(w) \ne sgn(u)$}{
      $b \gets c$ \;
      $v \gets w$ \;
    }
    \Else{
      $a \gets c$ \;
      $u \gets w$ \;
    }
  }
\end{algorithm}
\DecMargin{1em}
\IncMargin{1em}
\begin{algorithm}
  \caption{简化二分法实现算法}\label{algorithm2}
  \KwData{$f:[a,b] \to \mathbb{R}$, $a \in \mathbb{R}$, $b \in \mathbb{R}$, $M \in \mathbb{N}$, $\delta \in \mathbb{R}^+$, $\epsilon \in \mathbb{R}^+$
  }
  \KwResult{c, h, k}
  \BlankLine
  \emph{$h \gets b-a$}\;
  \emph{$u \gets f(a)$}\;
  \For{$k = 0:M$}{
    \emph{$h \gets h/2$}\;
    \emph{$c \gets a + h$}\;
    \lIf{$|h| < \delta$ or $k == M$}{break}
    \emph{$w \gets f(c)$}\;
    \uIf{$|w| < \epsilon$}{break}
    \ElseIf{$sgn(w) == sgn(u)$}{
      $a \gets c$ \;
    }
  }
\end{algorithm}
\DecMargin{1em}
二分法一阶线性收敛.
\subsection{[牛顿法]\textbf{Newton's method}}
\begin{algorithm}
  \caption{牛顿法实现算法}\label{algorithm3}
  \KwData{$f:[a,b] \to \mathbb{R}$, $f'$, $x_0 \in \mathbb{R}$, $M \in \mathbb{N}^+$, $\epsilon \in \mathbb{R}^+$}
  \KwResult{x, k}
  \BlankLine
  \emph{$x \gets x_0$}\;
  \For{$k = 0:M$}{
    \emph{$u \gets f(x)$}\;
    \lIf {$|u| < \epsilon$}{break}
    \emph{$x \gets x - u/f'(x)$}\;
  }
\end{algorithm}
牛顿法二阶收敛.
\subsection{[割线法]\textbf{The secant method}}
\begin{algorithm}
  \caption{割线法实现算法}\label{algorithm4}
  \KwData{$f:\mathbb{R} \to \mathbb{R}$, $x_0 \in \mathbb{R}$, $x_1 \in \mathbb{R}$, $M \in \mathbb{N}^+$, $\delta \in \mathbb{R}^+$, $\epsilon \in \mathbb{R}^+$}
  \KwResult{$x_n$, $x_{n-1}$, k}
  \BlankLine
  \emph{$x_n \gets x_1$}\;
  \emph{$x_{n-1} \gets x_0$}\;
  \emph{$u \gets f(x_n)$}\;
  \emph{$v \gets f(x_{n-1})$}\;
  \For{$k = 2:M$}{
    \emph{$s \gets \frac{x_n - x_{n-1}}{u - v}$}\;
    \emph{$x_{n-1} \gets x_n$}\;
    \emph{$v \gets u$}\;
    \emph{$x_n \gets x_n - u \times s$}\;
    \lIf{$|x_n - x_{n-1}| < \delta$}{break}
    \emph{$u \gets f(x_n)$}\;
    \lIf{$|u| < \epsilon$}{break}
  }
\end{algorithm}
割线法的收敛阶数为$\frac{1}{2}(1+\sqrt{5})$约等于1.618.
\end{document}
